package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author haomin
 * @date 2022/09/02 22:24
 **/
public class Day48_7_Offer41_MedianFinder {
    // 超时
    class MedianFinder1 {
        List<Integer> list;
        /** initialize your data structure here. */
        public MedianFinder1() {
            list = new ArrayList<>();
        }

        public void addNum(int num) {
            list.add(num);
        }

        public double findMedian() {
            int len = list.size();
            int[] arr = new int[len];
            for(int i = 0; i < len; ++i) {
                arr[i] = list.get(i);
                System.out.println(arr[i]);
            }
            Arrays.sort(arr);
            return len % 2 == 0 ? (double) arr[len/2] : (double) (arr[len/2]+arr[len/2+1])/2;
        }
    }
    // 大根堆+小根堆
    class MedianFinder {
        PriorityQueue<Integer> left;
        PriorityQueue<Integer> right;
        /** initialize your data structure here. */
        public MedianFinder() {
            left = new PriorityQueue<>((o1, o2) -> o2 - o1);
            right = new PriorityQueue<>();
        }

        public void addNum(int num) {
            left.add(num);
            right.add(left.poll());
            if(left.size() + 1 < right.size()){
                left.add(right.poll());
            }
        }

        public double findMedian() {
            if(left.size() < right.size()) return right.peek();
            return (double)(left.peek() + right.peek())/2;
        }
    }
}